/*
 * @Author: szx
 * @Date: 2022-04-04 14:26:04
 * @LastEditTime: 2022-04-04 14:33:58
 * @Description:
 * @FilePath: \leetcode\剑指offerII\030\030.js
 */
/**
 * Initialize your data structure here.
 */
 var RandomizedSet = function () {
    // numToLocation存储了每个数值及其在数组nums中的下标
    this.numToLocation = new Map();
    // 数值保存在动态数组nums中
    this.nums = [];
};

/**
 * Inserts a value to the set. Returns true if the set did not already contain the specified element.
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function (val) {
    // 如果数据集中之前已经包含该数值，则不能添加
    if (this.numToLocation.has(val)) {
        return false;
    }
    // 如果之前没有该数值，则把它添加到数组nums的尾部，并把它和它在数组中的下标添加到哈希表中
    this.numToLocation.set(val, this.nums.length);
    this.nums.push(val);
    return true;
};

/**
 * Removes a value from the set. Returns true if the set contained the specified element.
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function (val) {
    // 数据集中是否已经包含该数值，如果没有包含则不能删除
    if (!this.numToLocation.has(val)) {
        return false;
    }
    // 从哈希表中删除一个元素是O(1),
    let location = this.numToLocation.get(val);
    this.numToLocation.set(this.nums[this.nums.length - 1], location);
    this.numToLocation.delete(val);
    // 数组删除对应，这里是把数据最末位的元素覆盖要删除的元素，再把数组长度减1，通过这种技巧来达到时间复杂度为O(1)
    this.nums[location] = this.nums[this.nums.length - 1];
    this.nums.length--;
    return true;
};

/**
 * Get a random element from the set.
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function () {
    // 随机生成0到this.nums.length范围内的一个整数
    let p = parseInt(Math.random() * this.nums.length);
    return this.nums[p];
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * var obj = new RandomizedSet()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */
